101 Algorithms Questions You Must Know: Tricky Questions. Fun Solutions. by Arora Amrinder

Author:Arora, Amrinder [Arora, Amrinder]
Language: eng
Format: epub
Published: 2018-08-13T16:00:00+00:00

Question 59. Love (Skip) Thy Neighbor

Given a list of n positive numbers, your objective is to select the set of numbers that maximizes the sum of selected numbers, given the constraint that we cannot select two numbers that are located adjacent to each other. Describe a linear time algorithm for this problem.

Solution

Suppose the given array is a , with values a[1], .., a[n]. Let S(j) denote the maximum sum of numbers that can be achieved using first j numbers, such that no adjacent numbers are selected.

We observe that S(j) can be defined recursively as follows:

​ S(j) = max {S(j-1), S(j-2) + a[j] }

The two arguments in the max function correspond to the cases where we select (j – 1) -th element and forego j -th element, or we select j -th element and forego (j – 1) -th element.

This recursive relationship can be seeded with the following two base values:

S(1) = a[1]

S(2) = max{a[1], a[2]}

We observe that the principle of optimality clearly holds in this case, as if S(j) is optimal, then the sub-solutions S(j-1) and S(j-2) must be optimal as well.

Therefore, the following dynamic programming algorithm can be used.

S[1] = a[1]

S[2] = max{a[1], a[2]}

for j = 3 to n

S[j] = max {S[j-1], S[j-2]+a[j]

// Our final answer is S[n]

Download

Copyright Disclaimer:
This site does not store any files on its server. We only index and link to content provided by other sites. Please contact the content providers to delete copyright contents if any and email us, we'll remove relevant links or contents immediately.